package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/4ueAj6/
 * @create 2025/9/11 22:34
 * @since JDK17
 */

class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
public class Solution19 {

    public Node insert(Node head, int insertVal) {
        if (head == null) {
            return new Node(insertVal);
        }
        Node pre, p;
        if (head.val <= insertVal) {
            for (pre = head, p = head.next; p != head; pre = p, p = p.next) {
                if (p.val >= insertVal || pre.val > p.val) {
                    pre.next = new Node(insertVal, p);
                    break;
                }
            }
        } else {
            // 找到分界点
            for (pre = head, p = head.next; p != head; pre = p, p = p.next) {
                if (pre.val > p.val) {
                    break;
                }
            }

            for (; p != head.next; pre = p, p = p.next) {
                if (p.val >= insertVal) {
                    pre.next = new Node(insertVal, p);
                    break;
                }
            }
        }

        return head;
    }
}
